package IntervalSet.Medium;

import java.util.ArrayList;
import java.util.Comparator;

public class LC0435 {
    /**
     * 贪心解法，本质上是“最大不重叠区间数”问题。没有采用优化，时间复杂度应为N^2。
     */
    public static int eraseOverlapIntervalsGreedy(int[][] intervals) {
        ArrayList<ArrayList<Integer>> intervalsAsList = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            ArrayList<Integer> newList = new ArrayList<>();
            newList.add(intervals[i][0]);
            newList.add(intervals[i][1]);
            intervalsAsList.add(newList);
        }
        intervalsAsList.sort(Comparator.comparingInt((ArrayList<Integer> list) -> list.get(0))); // 第一个元素更小的排在前面

        int nIntervals = intervals.length;
        boolean[] picked = new boolean[nIntervals], skipped = new boolean[nIntervals];
        int skipCount = 0;
        for (int i = nIntervals - 1; i >= 0; i--) {
            if (skipped[i]) continue;

            picked[i] = true;
            ArrayList<Integer> pickedInterval = intervalsAsList.get(i);
            int start = pickedInterval.get(0), end = pickedInterval.get(1);
            // 排除重叠区间
            for (int j = i - 1; j >= 0; j--) {
                if (skipped[j] || picked[j]) continue;
                ArrayList<Integer> checkedInterval = intervalsAsList.get(j);
                if (checkedInterval.get(1) > start) {
                    skipped[j] = true;
                    skipCount++;
                }
            }
        }

        return skipCount;
    }

    public static void main(String[] args) {
        int[][] intervals = new int[][]{{1, 100}, {11, 22}, {1, 11}, {2, 12}};
        System.out.println(eraseOverlapIntervalsGreedy(intervals));
    }
}
